package com.jz;

/**
 * Description: JZ47 礼物的最大价值
 *
 * @author weiruibai.vendor
 * Date: 2022/9/23 10:00
 */
public class JZ47 {

    /**
     * [[9,1,4,8]]
     * <p>
     * [[1,3,1],[1,5,1],[4,2,1]]
     *
     * @param args
     */
    public static void main(String[] args) {
        JZ47 jz47 = new JZ47();
        int[][] grid = new int[][]{{9, 1, 4, 8}};
        grid = new int[][]{{1, 3, 1}, {1, 5, 1}, {4, 2, 1}};
        System.out.println(jz47.maxValue_v1(grid));
        System.out.println(jz47.maxValue_dp(grid));
    }

    /**
     * 暴力递归
     * 总结规律
     *
     * @param grid
     * @return
     */
    public int maxValue_v1(int[][] grid) {
        int ans = 0;
        ans = process(grid, 0, 0);
        return ans;
    }


    private int process(int[][] grid, int i, int j) {
        if (i >= grid.length || j >= grid[0].length) {
            return 0;
        }
        if (i == grid.length - 1 && j == grid[0].length - 1) {
            return grid[i][j];
        }
        // 右
        int ans1 = process(grid, i, j + 1);
        // 下
        int ans2 = process(grid, i + 1, j);
        return grid[i][j] + Math.max(ans1, ans2);
    }

    /**
     * 看maxValue_v1
     * 发现dp当前位置的值，由数组当前位置的右边值和下边值的最大值+数组当前位置的值
     *
     * @param grid
     * @return
     */
    public int maxValue_dp(int[][] grid) {
        int N = grid.length;
        int M = grid[0].length;
        int[][] dp = new int[N][M];
        dp[N - 1][M - 1] = grid[N - 1][M - 1];
        // 填充最后1列
        for (int i = N - 2; i >= 0; i--) {
            dp[i][M - 1] = grid[i][M - 1] + dp[i + 1][M - 1];
        }
        // 填充最后1行
        for (int i = M - 2; i >= 0; i--) {
            dp[N - 1][i] = grid[N - 1][i] + dp[N - 1][i + 1];
        }
        for (int i = N - 2; i >= 0; i--) {
            for (int j = M - 2; j >= 0; j--) {
                // 由数组当前位置的右边值和下边值的最大值+数组当前位置的值
                dp[i][j] = grid[i][j] + Math.max(dp[i + 1][j], dp[i][j + 1]);
            }
        }
        return dp[0][0];
    }

}
